package code.mySpecializedTraining;

/**
 * @author 26029
 * @date 2025/4/18
 * @description
 */
public class BinarySearch {
    // 704. 二分查找
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int pos = -1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (target == nums[mid]) {
                pos = mid;
                break;
            } else if (target > nums[mid])
                left = mid + 1;
            else
                right = mid - 1;
        }
        return pos;
    }

    // 35. 搜索插入位置
    public int searchInsert(int[] nums, int target) {
        // 插入位置,即大于等于target的最小位置
        int left = 0, right = nums.length - 1;
        int pos = nums.length;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] >= target) {
                pos = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return pos;
    }

    // 744. 寻找比目标字母大的最小字母
    public char nextGreatestLetter(char[] letters, char target) {
        // 大于target的最小位置
        int left = 0, right = letters.length - 1;
        int pos = letters.length;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (letters[mid] > target) {
                pos = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (pos == letters.length)
            return letters[0]; // 题目规定
        else
            return letters[pos];
    }

    // 34. 在排序数组中查找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        // 这道题不是求插入位置，故，当不等于时，不用给目标答案位置赋值
        int left = 0, right = nums.length - 1;
        int firstPos = nums.length, lastPos = -1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == target) {
                firstPos = mid;
                right = mid - 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (firstPos == nums.length)
            return new int[]{-1, -1};
        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == target) {
                lastPos = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return new int[]{firstPos, lastPos};
    }

    // 33. 搜索旋转排序数组
    public int search_33(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int ans = -1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == target) {
                ans = mid;
                break;
            }
            // 如果[left, mid]是正常的
            if (nums[mid] >= nums[left]) {
                // 4 5 6 7 8 9 0 1 2 3
                if (nums[left] <= target && target <= nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            // 如果[mid, right]是正常的
            else {
                if (nums[mid] <= target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return ans;
    }

    // 153. 寻找旋转排序数组中的最小值
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        int min = Integer.MAX_VALUE;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            // 如果左面正常,说明min要么在右面,要么是left
            if (nums[left] <= nums[mid]) {
                min = Math.min(min, nums[left]);
                left = mid + 1;
            }
            // 如果右面正常,说明min要么是mid,要么在左面
            else {
                min = Math.min(min, nums[mid]);
                right = mid - 1;
            }
        }
        return min;
    }

    // 154. 寻找旋转排序数组中的最小值 II
    public int findMin_(int[] nums) {
        int left = 0, right = nums.length - 1;
        int min = Integer.MAX_VALUE;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            // 元素可重复,考虑[2,0,2,2,2]这种情况
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                min = Math.min(min, nums[mid]);
                left++;
                right--;
            }
            // 如果左面正常,说明min要么在右面,要么是left
            else if (nums[left] <= nums[mid]) {
                min = Math.min(min, nums[left]);
                left = mid + 1;
            }
            // 如果右面正常,说明min要么是mid,要么在左面
            else {
                min = Math.min(min, nums[mid]);
                right = mid - 1;
            }
        }
        return min;
    }

    // 4. 寻找两个正序数组的中位数
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 如果是5个，找第3小的数字；如果是6个，找第3和第4小的数字
        int n = nums1.length, m = nums2.length;
        int sum = n + m;  //总数量
        double ans = 0;
        if (sum % 2 == 1)
            ans = findKthMin(sum / 2 + 1, nums1, 0, n - 1, nums2, 0, m - 1);
        else
            ans = (double) (findKthMin(sum / 2, nums1, 0, n - 1, nums2, 0, m - 1)
                    + findKthMin(sum / 2 + 1, nums1, 0, n - 1, nums2, 0, m - 1)) / 2;
        return ans;
    }

    // 递归找到第k小的数字
    private int findKthMin(int k, int[] nums1, int start1, int end1, int[] nums2, int start2, int end2) {
        // 递归退出条件1：其中一个数组到头了
        if (start1 > end1)
            return nums2[start2 + k - 1];
        if (start2 > end2)
            return nums1[start1 + k - 1];
        // 递归退出条件2：k=1
        if (k == 1)
            return Math.min(nums1[start1], nums2[start2]);

        int pos1 = Math.min(end1, start1 + k / 2 - 1); // 从start1开始的第k/2个
        int pos2 = Math.min(end2, start2 + k / 2 - 1);
        if (nums1[pos1] < nums2[pos2])
            return findKthMin(k - (pos1 - start1 + 1), nums1, pos1 + 1, end1, nums2, start2, end2);
        else
            return findKthMin(k - (pos2 - start2 + 1), nums1, start1, end1, nums2, pos2 + 1, end2);
    }

    public static void main(String[] args) {
        BinarySearch search = new BinarySearch();
        System.out.println(search.findMedianSortedArrays(new int[]{2, 2, 4, 4}, new int[]{2, 2, 2, 4, 4}));
    }
}
